The bilateral filter is a non-linear filter introduced by Tomasi and Manduchi (see “Bilateral filtering for gray and color images”, Proc. IEE Intl. Conf. on Computer Vision, Bombay, India, 1998), which is used for selective denoising of images without blurring image edges. The bilateral filter is based on the idea of modifying the weights of a convolution mask in an image dependent manner, as a function of intensity differences between a pixel under consideration and its neighbors. While the original convolution weights sum to one (as required from any mean-preserving filter), the sum of the modified weights is less than one, so that in order to retain the local normalization of the modified convolution weights, the convolution result is divided by the sum of the modified weights. This single division operation considerably increases the computational complexity necessary to implement a bilateral filter with a digital processor. In addition, in hardware implementations it forces the inclusion of an integer division circuit which would be otherwise unnecessary.
In implementing a bilateral filter, the DIVIDE operation has a large relative cost in actual computation time. As a typical example, one benchmark program shows that on a Pentium-III processor, integer ADD or SUBTRACT operations take a single clock cycle, while an integer MULTIPLY takes 5 cycles, a lookup-table operation takes 3 cycles, and an integer DIVIDE takes as much as 47 clock cycles. Thus, with the Pentium-III processor, the cycle count would be 19N+47. For a typical case of a 3×3 (pixel matrix) neighborhood support, N is equal to 8, so that the single division operation takes about 24 percent of the cycles needed for the entire calculation. This relative percentage may vary when other processors are used, but in any case the single division operation takes a considerable fraction of the entire calculation. It is thus desirable to eliminate this single DIVIDE operation.
Therefore, what is needed is a method by which a computer or other digital processor may implement a bilateral filter without performing any division operations.